#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node
{
    char *key;
    char **values;
    int count;
};

struct Node *createNode(char *key, char *value)
{
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->key = strdup(key);
    node->values = (char **)malloc(sizeof(char *));
    node->values[0] = strdup(value);
    node->count = 1;
    return node;
}

void sortString(char *str)
{
    int n = strlen(str);
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (str[i] > str[j])
            {
                char temp = str[i];
                str[i] = str[j];
                str[j] = temp;
            }
        }
    }
}

char ***groupAnagrams(char **strs, int strsSize, int *returnSize, int **returnColumnSizes)
{
    char ***ret = NULL;
    struct Node **map = (struct Node **)malloc(strsSize * sizeof(struct Node *));
    int mapSize = 0;
    int i, j;

    for (i = 0; i < strsSize; i++)
    {
        char *key = strdup(strs[i]);
        sortString(key);

        int found = 0;
        for (j = 0; j < mapSize; j++)
        {
            if (strcmp(map[j]->key, key) == 0)
            {
                map[j]->values = (char **)realloc(map[j]->values, (map[j]->count + 1) * sizeof(char *));
                map[j]->values[map[j]->count] = strdup(strs[i]);
                map[j]->count++;
                found = 1;
                break;
            }
        }

        if (!found)
        {
            map[mapSize] = createNode(key, strs[i]);
            mapSize++;
        }
    }

    ret = (char ***)malloc(mapSize * sizeof(char **));
    *returnColumnSizes = (int *)malloc(mapSize * sizeof(int));

    for (i = 0; i < mapSize; i++)
    {
        (*returnColumnSizes)[i] = map[i]->count;
        ret[i] = (char **)malloc(map[i]->count * sizeof(char *));

        for (j = 0; j < map[i]->count; j++)
        {
            ret[i][j] = strdup(map[i]->values[j]);
        }
    }

    *returnSize = mapSize;

    // Free memory
    for (i = 0; i < mapSize; i++)
    {
        free(map[i]->key);
        for (j = 0; j < map[i]->count; j++)
        {
            free(map[i]->values[j]);
        }
        free(map[i]->values);
        free(map[i]);
    }
    free(map);

    return ret;
}

int main()
{
    int i, j;
    // char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    // char *strs[] = {""};
    char *strs[] = {"a"};
    int strsSize = 1;
    int returnSize;
    int *returnColumnSizes;
    char ***ret = groupAnagrams(strs, strsSize, &returnSize, &returnColumnSizes);

    for (i = 0; i < returnSize; i++)
    {
        for (j = 0; j < returnColumnSizes[i]; j++)
        {
            printf("%s ", ret[i][j]);
        }
        printf("\n");
    }

    // Free memory
    for (i = 0; i < returnSize; i++)
    {
        for (j = 0; j < returnColumnSizes[i]; j++)
        {
            free(ret[i][j]);
        }
        free(ret[i]);
    }
    free(ret);
    free(returnColumnSizes);

    return 0;
}